#ifndef _MAIN_H
#define _MAIN_H

#include <iostream>
#include <vector>
#include <algorithm>

struct Node
{
    //起始地址，占用大小
    unsigned long long start_address,size;
    bool operator < (const Node &node)
	{
		return size < node.size;
	}
};

struct Node1
{
    //起始地址，占用大小,是否使用
    unsigned long long start_address,size,is_used;
    bool operator < (const Node1 &node)
	{
		return start_address < node.start_address;
	}
};

class best_fit_algorithm
{
    //默认limit=1024KB,系统占用内存为256KB.
    public:
        Node add_use(unsigned long long use_size)
        {
            for(int i=0;i<FREE_RAM.size();i++)
            {
                if(FREE_RAM[i].size >= use_size)
                {
                    Node used = {FREE_RAM[i].start_address,use_size};
                    Node now = {FREE_RAM[i].start_address + use_size,FREE_RAM[i].size - use_size};
                    USED_RAM.push_back(used);
                    FREE_RAM.erase(FREE_RAM.begin()+i);
                    if(FREE_RAM[i].size > use_size)
                        FREE_RAM.push_back(now);
                    std::sort(FREE_RAM.begin(),FREE_RAM.end());
                    std::cout<<"申请内存成功！"<<std::endl;
                    return used;
                }
            }
            std::cout<<"申请内存失败！"<<std::endl;
            return {0,0};
        }
        void merge_RAM()
        {
            std::sort(FREE_RAM.begin(),FREE_RAM.end(),[](Node x, Node y){return x.start_address < y.start_address;});
            for(int i=1;i<FREE_RAM.size();i++)
            {
                if(FREE_RAM[i].start_address==FREE_RAM[i-1].start_address+FREE_RAM[i-1].size)
                {
                    FREE_RAM[i-1].size+=FREE_RAM[i].size;
                    FREE_RAM.erase(FREE_RAM.begin()+i);
                    i--;
                }
            }
        }
        Node release_used(unsigned long long start_address,unsigned long long size)
        {
            if(start_address+size >= limit)
            {
                std::cout<<"释放内存失败！"<<std::endl;
                return {0,0};
            }
            for(int i = 0; i < USED_RAM.size(); i ++ )
            {
                if(start_address == USED_RAM[i].start_address && size == USED_RAM[i].size)
                {
                    USED_RAM.erase(USED_RAM.begin()+i);
                    FREE_RAM.push_back({start_address,size});
                    merge_RAM();
                    std::sort(FREE_RAM.begin(),FREE_RAM.end());
                    return {start_address,size};
                }
            }
            std::cout<<"释放内存失败！"<<std::endl;
            return {0,0};
        }
        best_fit_algorithm()
        {
            USED_RAM.push_back({0,256});
            FREE_RAM.push_back({256,limit-256});
        }
        best_fit_algorithm(unsigned long long set_size)
        {
            limit = set_size;
            USED_RAM.push_back({0,256});
            FREE_RAM.push_back({256,limit-256});
        }
        void show()
        {
            RAM.clear();
            for(auto i:FREE_RAM) RAM.push_back({i.start_address,i.size,0});
            for(auto i:USED_RAM) RAM.push_back({i.start_address,i.size,1});
            std::sort(RAM.begin(),RAM.end());
            printf("--------------内存使用情况------------------\n");
            printf("分区号    起始地址      占用大小     分配情况\n");
            for(int i = 0; i < RAM.size(); i ++ )
            {
                printf("%-10d %-10llu %-10llu",i,RAM[i].start_address,RAM[i].size);
                if(RAM[i].is_used) printf("已分配\n");
                else printf("空闲\n");
            }
        }
    private:
        std::vector<Node> FREE_RAM,USED_RAM;
        std::vector<Node1> RAM;
        unsigned long long limit=1024;
};

#endif
